המבנה האבסטרקטי Disjoint sets:

• מנהל אוסף C של קבוצות שאין ביניהן חיתוך (זרות))
• כל קבוצה באוסף C מזוהה על ידי איבר המשמש כנציג של אותה קבוצה.
• פעולות:
  • פעולת MakeSet(x):
    • יוצרת קבוצה חדשה המכילה איבר בודד x ומוסיף אותה לאוסף C.
  • פעולת Union(x,y):
    • מאחדת את הקבוצה שמכילה x עם הקבוצה שמכילה את y לקבוצה חדשה.
    • הנציג של הקבוצה החדשה יכול להיות כל אחד מהאיברים.
    • הפעולה מניחה שהקבוצות היו זרות לפני האיחוד.
  • פעולת FindSet(x):
    • פעולה המקבלת איבר ומחזיר מצביע לנציג של הקבוצה שמכילה את האיבר x.
  • 

שימוש במציאת רכיבי קשירות (Connected Components):

• יישום של מבנה זה הוא פירוק של גרף לרכיבי הקשירות שלו בשני שלבים:
  • שלב ראשון: רצים על כל הקודקודים ומבצעים עליהם MakeSet.
  • שלב שני: רצים על כל הצלעות בגרף, ואם שני קודקודים לא נמצאים באותה קבוצה, מבצעים איחוד.
• כעת, נוכל לבדוק שייכות, אם נרצה לדעת האם שני קודקודים נמצאים באותו רכיב קשירות, נוכל לבדוק באמצעות FIndSet על שניהם.

ייצוג באמצעות רשימה מקושרת:

• כל קבוצה נשמרת כרשימה, כאשר ישנו אובייקט set המחזיק מצביעים לאיבר הראשון ולאיבר האחרון.
• הנציג של הקבוצה הוא האיבר הראשון ברשימה, וכל איבר מחזיק בנוסף מצביע לאובייקט הקבוצה שלו.
• 
• סיבוכיות פעולות:
  • פעולת MakeSet: מתבצעת בזמן $\mathrm{\Theta }(1)$.
  • פעולת FindSet: מתבצעת בזמן $\mathrm{\Theta }(1)$
  • פעולת Union:
    • משרשרת את הרשימה של y לסוף הרשימה של x ומעדכנת מצביעים.
    • סיבוכיות הריצה היא $\mathrm{\Theta }(n)$ במקרה הגרוע וגם בניתוח לשיעורין.
• שיפור זמן הריצה באמצעות איחוד לפי משקל:
  • הזמן לפעולת union בודדת הוא $\mathrm{\Theta }(n)$, ומספר פעולות של MakeSet ו - Union יכול להגיע גם ל $\mathrm{\Theta }(n^2)$.
  • נשמור בנוסף את שדה ה - size של כל קבוצה, ותמיד נשרשר את הרשימה הקטנה יותר לרשימה הגדולה יותר.
  • במצב זה, הזמן במקרה הגרוע ישאר $\mathrm{\Theta }(n)$ לפעולה בודדת, אך עובר סדרה של m פעולות, (שמתוכן n פעולות Union), סיבוכיות הזמן תהיה $\mathrm{\Theta }(m+nlogn)$

ייצוג באמצעות יערות:

• כל קבוצה מיוצגת בעזרת עץ, הנציג של הקבוצה הוא שורש העץ, אשר תמיד מצביע לעצמו.
• כל צומת מכיל מצביע לאבא שלו בלבד, ללא מצביעים לילדיו.
• סיבוכיות הפעולות:
  • פעולת makeSet: יוצר עץ חדש ב $\mathrm{\Theta }(1)$.
  • פעולת FindSet: מטפס בעץ עד לשורש ומחזיר אותו, במקרה הגרוע $\mathrm{\Theta }(n)$.
  • פעולת Union: קובע את שורש העץ של y להיות אבא של העץ של x ב $\mathrm{\Theta }(n)$
• שיפור זמן הריצה:
  • ניתן לשפר את הסיבוכיות באמצעות שילוב של שתי שיטות:
    • איחוד לפי גובה / דרגה:
      • כל שורש שומר משתנה של דרגה או גובה.
      • כאשר מבצעים איחוד, גורמים לשורש בעל הגובה הקטן יותר להצביע לשורש בעל הגובה הגדול יותר.
      • כעת גובה העצץ חסום ב $\mathrm{\Theta }(\log (n))$ ומקטין את זמן הריצה של $\mathrm{\Theta }(n)$
      • כאשר משתמשים גם בטכניקה הבאה, שומרים משתנה דרגה המהווה חסם עליון בלבד לגובה העץ.
    • דחיסת מסלולים:
      • בכל פעם שמבצעים FIndSet, משנים את כל מצביעי האב של הקודקודים במסלול מ-x אל השורש, כך שיצביעו באופן ישיר אל שורש העץ.
      • 
  • שילוב שתי השיטות מבטיח שעבור פעולה בודדת של Union או FindSet זמן הריצה יהיה $\mathrm{\Theta }(n)$, אך עבור סדרה ארוכה של פעולות, הזמן עומד על $\mathrm{\Theta }(m\cdot \alpha (n))$ במקרה הגרוע, כאשר $\alpha (n)$ היא פונקציית אקרמן ההפוכה אשר גדלה לאט באופן קיצוני ומבטיחה זמן פעולה משוקלל של $\mathrm{\Theta }(1)$.

תובנות מהתרגול:

• בייצוג באמצעות יער עצים צריך גם איחוד לפי דרגות וגם כיווץ מסלולים